// 时间复杂度: O((m+n)log(m+n))
// 空间复杂度: O(m+n)
// 分析：
// 1. 合并数组 [...nums1, ...nums2]: O(m+n)
// 2. 排序 .sort(): O((m+n)log(m+n))
// 3. 访问中位数: O(1)
function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
    const newArr = [...nums1, ...nums2].sort((a, b) => a - b);
    const n = Math.floor(newArr.length / 2);
    const a = newArr.length % 2;

    if (a === 0) {
        return (newArr[n - 1] + newArr[n]) / 2;
    }
    return newArr[n];
}

// 算法的时间复杂度应该为 O(log (m+n))
function findMedianSortedArrays2(nums1: number[], nums2: number[]): number {
    // 确保 nums1 是较短的数组，这样我们可以减少二分查找的范围
    if (nums1.length > nums2.length) {
        [nums1, nums2] = [nums2, nums1];
    }
    const m = nums1.length;
    const n = nums2.length;
    const totalLength = m + n;
    const halfLength = Math.floor((totalLength + 1) / 2); //预期左边的元素个数

    let left = 0;
    let right = m;

    while (left <= right) {
        // 在 nums1 中找到一个分割点 i
        const i = Math.floor((left + right) / 2);
        // 根据 i 计算 nums2 中的分割点 j
        const j = halfLength - i;

        // 计算分割线两边的值
        const nums1Left = i > 0 ? nums1[i - 1] : -Infinity;
        const nums1Right = i < m ? nums1[i] : Infinity;
        const nums2Left = j > 0 ? nums2[j - 1] : -Infinity;
        const nums2Right = j < n ? nums2[j] : Infinity;

        // 检查：所有左边元素 ≤ 所有右边元素
        if (nums1Left <= nums2Right && nums2Left <= nums1Right) {
            // 找到正确的分割线
            if (totalLength % 2 === 1) {
                // 总长度为奇数，中位数是左边最大值
                return Math.max(nums1Left, nums2Left);
            } else {
                // 总长度为偶数，中位数是左边最大值和右边最小值的平均值
                return (
                    (Math.max(nums1Left, nums2Left) +
                        Math.min(nums1Right, nums2Right)) /
                    2
                );
            }
            // 调整二分查找范围;
        } else if (nums1Left > nums2Right) {
            // 分割线太靠右了，向左移动
            right = i - 1;
        } else {
            // 分割线太靠左了，向右移动
            left = i + 1;
        }
    }
    throw new Error('Input arrays are not sorted');
}

/**
 * 通用解法
 * [1,2,3] 奇数，k=floor((3+1)/2)=2,中位数是左边最大值[1,2] 就是2
 * [1,2,3,4] 偶数，k=floor((4+1)/2)=2,中位数是左边最大值[1,2]:2和右边最小值[3,4]:3的平均值，
 *
 *
 * n1: [1,2]
 * n2: [3]
 * 预期：[1,2,3]
 * k=floor((3+1)/2)=2，按理需要左边有两个元素
 * 情况1.分割线在n1的0下标时（左边没有元素），n2就应该是k-0=2个元素
 * 左边：[]+[3],左边只有一个元素，不满足
 * 情况2.分割线在n1的1下标时（左边有1个元素），n2就应该是k-1=1个元素
 * 左边：[1]+[3],左边有2个元素，满足，右边：[2]，但是不满足左边最大值3<=右边最小值2
 * 情况3.分割线在n1的2下标时（左边有2个元素，右边没有元素),n2就应该是k-2=0个元素
 * 左边：[1,2]+[],左边有2个元素，满足，右边：[3]，满足左边最大值2<=右边最小值3
 * 判断奇偶：3%2=1，奇数，直接取左边最大值是2，中位数是2
 *
 * [1,3,5,7] [2,4,6,8,9]
 * 8+1 /2 =4
 * [3,5] [4,6] 5+4 /2 = 4.5
 *
 * 9+1 /2 =5
 * [3,5] [6,8]  右移
 * [5,7] [4,6] 左边的值[5,4],奇数就取左边最大值5
 *
 * [1,2,3,4,5,6] [7,8,9]
 * 9+1 /2 =5  n1:6/2 =3 n2: 5-3=2
 * [3,4] [8,9] 不满足所有左边<=所有右边 ，右移 i+1,left:4 n1:4 n2:1
 * [4,5] [7,8] 不满足所有左边<=所有右边 ，右移 n1:5 n2:0
 * [5,6] [ -Infinity,7] 满足所有左边<=所有右边，奇数取左边最大值5
 *
 * [7,8,9] [1,2,3,4,5,6]
 * 9+1 /2 =5  n1:3/2 =1 n2: 5-1=4
 * [7,8] [4,5] 不满足所有左边<=所有右边，左移 n1:0 n2:5
 * [ -Infinity,7] [5,6] 满足所有左边<=所有右边，奇数取左边最大值5
 * left2 > right1 右移 left2大则n2的分割线应该往左，那么n1的分割线就应该往右
 * left1 > right2 左移 left1大则n1的分割线应该往左
 *
 *
 *
 *
 */

function fn(nums1: number[], nums2: number[]): number {
    if (nums1.length > nums2.length) {
        return fn(nums2, nums1);
    }

    const m = nums1.length;
    const n = nums2.length;
    const len = m + n;
    let low = 0;
    let high = m;
    const half = Math.floor((len + 1) / 2);

    while (low < high) {
        const i = Math.floor((low + high) / 2); //二分法
        const j = half - i;

        const nums1Left = i === 0 ? -Infinity : nums1[i - 1];
        const nums1Right = i === m ? Infinity : nums1[i];
        const nums2Left = j === 0 ? -Infinity : nums2[j - 1];
        const nums2Right = j === n ? Infinity : nums2[j];

        if (nums1Left <= nums2Right && nums2Left <= nums1Right) {
            if (len % 2 === 0) {
                return (
                    (Math.max(nums1Left, nums2Left) +
                        Math.min(nums1Right, nums2Right)) /
                    2
                );
            } else {
                return Math.max(nums1Left, nums2Left);
            }
        } else if (nums1Left > nums2Right) {
            high = i - 1;
        }else{
            low = i + 1;
        }
    }

     throw new Error('数组未排序！');
}
